#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<initializer_list>
using namespace std;

vector<int> runningSum(vector<int>& nums) {
    for (int i = 1; i < nums.size(); ++i)
    {
        nums[i] = nums[i] + nums[i - 1];
    }
    return nums;
}

int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right)
    {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] > target) right = mid - 1;
        else if (nums[mid] < target) left = mid + 1;
        else return mid;
    }
    return right + 1;
}

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    int n1 = nums1.size(), n2 = nums2.size();
    int cur1 = 0, cur2 = 0;
    vector<int> ans;
    while (cur1 < n1 && cur2 < n2)
    {
        if (nums1[cur1] < nums2[cur2]) ++cur1;
        else if (nums1[cur1] > nums2[cur2]) ++cur2;
        else
        {
            ans.push_back(nums1[cur1]);
            ++cur1, ++cur2;
        }
        while (cur1 > 0&&cur1 < n1 && nums1[cur1] == nums1[cur1 - 1]) ++cur1;
        while (cur2 > 0&&cur2 < n2 && nums2[cur2] == nums2[cur2 - 1]) ++cur2;
    }
    return ans;
}

int main()
{
    vector<int> v1{ (1,2,2,1) };
    vector<int> v2{ (2,2) };
    intersection(v1,v2);
}

int totalFruit(vector<int>& fruits) {
    int hash[100001] = { 0 };
    int n = fruits.size();
    int ret = 0;
    for (int left = 0, right = 0, kinds = 0; right < n; ++right)
    {
        if (hash[fruits[right]] == 0)
            ++kinds;
        ++hash[fruits[right]];
        while (kinds > 2)
        {
            --hash[fruits[left]];
            if (hash[fruits[left]] == 0)
                --kinds;
            left++;
        }
        ret = max(ret, right - left + 1);
    }
    return ret;
}